import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution1 {
    public boolean[] col;
    public boolean[] dig1;
    public boolean[] dig2;
    public List<List<String>> ret;
    public char[][] path;
    public int n;

    public List<List<String>> solveNQueens(int _n) {
        n = _n;
        col = new boolean[n];
        dig1 = new boolean[2 * n];
        dig2 = new boolean[2 * n];
        ret = new ArrayList<>();
        path = new char[n][n];

        for(int i = 0; i < n; i++) {
            Arrays.fill(path[i],'.');
        }

        dfs(0);
        return ret;
    }

    public void dfs(int x) {
        if(x == n) {
            // 添加结果
            List<String> tmp = new ArrayList<>();
            for(int i = 0; i < n; i++) {
                tmp.add(new String(path[i]));
            }
            ret.add(new ArrayList<>(tmp));
            return;
        }

        for(int y = 0; y < n; y++) {
            // 判断能不能放
            if(col[y] == false && dig1[y - x + n] == false && dig2[y + x] == false) {
                path[x][y] = 'Q';
                col[y] = true;
                dig1[y - x + n] = true;
                dig2[y + x] = true;

                dfs(x + 1);
                // 恢复现场
                col[y] = false;
                dig1[y - x + n] = false;
                dig2[y + x] = false;

            }
        }
    }
}